package addition;

/**
 * 1、 编写程序，给数组排序
 * 数组如下：
 * int a[] = {2, 4, 3, 1, 8, 9, 7, 6, 5};
 */
public class Q1 {

    /**
     * 冒泡排序
     *
     * @param origin 原数组
     * @return 排序后数组
     */
    public static int[] bubbleSort(int[] origin) {
        boolean flag = true;
        int len = origin.length, tmp;
        for (int i = 1; i < len; i++) {  // var i is control loop times
            for (int j = 0; j < len - i; j++) {  // var j is control sub loop range
                if (origin[j] > origin[j + 1]) {
                    tmp = origin[j];
                    origin[j] = origin[j + 1];
                    origin[j + 1] = tmp;
                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }

        return origin;
    }

    /**
     * 快速排序
     *
     * @param origin 原数组
     * @return 排序后数组
     */
    public static int[] fastSort(int[] origin) {

        return null;
    }

    /**
     * 插入排序
     *
     * @param origin 原数组
     * @return 排序后数组
     */
    public static int[] insertSort(int[] origin) {
        int len = origin.length, tmp, preIdx, current;
        for (int i = 1 /* assume 0 element was sorted */; i < len; i++) {  // var i is control loop times
            preIdx = i - 1;
            current = origin[i];
            while (preIdx >= 0 && origin[preIdx] > current) {  // find max insert index
                origin[preIdx + 1] = origin[preIdx];
                preIdx--;
            }

            origin[preIdx + 1] = current;
        }

        return origin;
    }

    /**
     * 希尔排序
     *
     * @param origin 原数组
     * @return 排序后数组
     */
    public static int[] shellSort(int[] origin) {
        int len = origin.length;
        for (int i = (int) Math.floor(len * 1.0 / 2); i > 0; i = (int) Math.floor(i * 1.0 / 2)) {

        }

        return null;
    }

    /**
     * 选择排序
     *
     * @param origin 原数组
     * @return 排序后数组
     */
    public static int[] selectSort(int[] origin) {
        int minIdx, tmp, len = origin.length;
        for (int i = 0; i < len; i++) {  // var i is control loop times
            minIdx = i;
            for (int j = i + 1 /* front i was sorted */; j < len; j++) {  // var j is find min sub index
                if (origin[minIdx] > origin[j]) {
                    minIdx = j;
                }
            }

            // i element exchange with min element
            tmp = origin[minIdx];
            origin[minIdx] = origin[i];
            origin[i] = tmp;
        }

        return origin;
    }

}
